Tìm thấy được các công cụ bằng đá cổ đại tại tỉnh Zamboanga del Norte, có thể cho thấy một nền văn hoá đồ đá mới. Trong các hang động tìm thấy các bình tuỳ táng, cùng với đồ sứ Trung Hoa và đồ trang sức bằng vàng. Từ khoảng thế kỷ 10, cư dân Mindanao chịu tác động mạnh trước ảnh hưởng và đức tin Ấn Độ giáo-Phật giáo đến từ Indonesia và Malaysia. Các loại chữ viết Ấn Độ hoá như Kawi và Baybayin được đưa đến từ Sulawesi và Java, các phương pháp dệt nhuộm batik và ikat cũng được đưa đến. Bước tiến triển văn hoá Ấn Độ giáo-Phật giáo mạnh mẽ nhất là tại các khu vực duyên hải của đảo, song tại các bộ lạc sống ở xa trong đất liền thì nó được hợp nhất với các đức tin và phong tục thuyết vật linh. Vương quốc Butuan là một quốc gia Ấn Độ giáo hoàn toàn, được ghi nhận trong sử sách Trung Hoa vào thế kỷ 10 với tư cách là nước triều cống, tập trung dọc bờ biển đông bắc của đảo xung quanh Butuan.[7]

Hồi giáo bắt đầu được truyền bá đến Philippines từ thế kỷ 14, hầu hết là bởi các thương gia Hồi giáo đến từ phần phía tây của quần đảo Mã Lai. Thánh đường Hồi giáo đầu tiên tại Philippines được xây dựng vào giữa thế kỷ 14 tại thị trấn Simunul.[7] Khoảng thế kỷ 16, các vương quốc Hồi giáo: Sulu, Lanao và Maguindanao được hình thành từ các vương quốc Ấn Độ giáo-Phật giáo trước đó. Đến khi Hồi giáo có được chỗ đứng tại hầu khắp Mindanao, cư dân bản địa sống trong các vương quốc Hồi giáo phải cải sang Hồi giáo hoặc bị buộc phải cống nạp cho những quân chủ Hồi giáo mới.

Ngày 2 tháng 2 năm 1543, Ruy Lopez de Villalobos là người Tây Ban Nha đầu tiên đến Mindanao,[8] ông gọi đảo là "Caesarea Caroli" theo Karl V của đế quốc La Mã Thần thánh (Carlos I của Tây Ban Nha). Không lâu sau khi thuộc địa hoá Cebu, người Tây Ban Nha tiến hành thuộc địa hoá Butuan và khu vực Caraga xung quanh tại phần đông bắc của Mindanao và phát hiện người Hồi giáo hiện diện đáng kể trên đảo. Theo thời gian, nhiều bộ lạc tại Mindanao cải sang Công giáo La Mã và xây dựng các khu dân cư và thành trì khắp các khu vực duyên hải trên đảo. Các khu dân cư này tồn tại trước các cuộc tấn công từ những vương quốc Hồi giáo lân cận. Khu định cư kiên cố nhất trong số đó là thành phố Zamboanga.[9] Đến cuối thế kỷ 18, Tây Ban Nha chi phối khắp đảo, lập các khu định cư và thành trì trên hầu khắp Mindanao, họ tiếp tục giao tranh với các vương quốc Hồi giáo cho đến cuối thế kỷ 19.[9]

Theo Hiệp định Paris năm 1898, Hoa Kỳ tiếp quản Philippines từ Tây Ban Nha, sau đó Hoa Kỳ ký các văn kiện phân chia rõ ràng ranh giới giữa nhóm đảo Mindanao với Borneo. Năm 1939, chính phủ Philippines khuyến khích cư dân từ Luzon và Visayas di cư đến Mindanao, hầu hết là người Ilocano, Cebuano và Illongo.

Trong Chiến tranh thế giới thứ hai, nhiều thành thị tại Mindanao bị phá huỷ hoàn toàn, đáng chú ý nhất là thành phố Davao, thành phố Zamboanga, Lanao, Cagayan de Oro, Iligan và Butuan.[10] Trong các tháng 4-5 năm 1942, Nhật Bản đánh bại binh sĩ Hoa Kỳ trên đảo trong một trận đánh bắt đầu tại Malabang. Các binh sĩ Philippines và du kích địa phương tích cực chống lại Nhật Bản cho đến khi đảo được giải phóng trong trận Mindanao.[11] Các vụ xung đột bạo lực tại phần tây nam của Mindanao bắt đầu từ thập niên 1960, dẫn tới việc thành lập Mặt trận Giải phóng Dân tộc Moro (MILF), và việc thành lập Ilaga.[12]